package com.czk.tree.traverse;

import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/10/11 10:09
 */
public class IteratorTraverse {
    public static void main(String[] args) {
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node2 = new Node(2, node4, node5);
        Node node3 = new Node(3, node6, node7);
        Node node1 = new Node(1, node2, node3);
        node1.preTraverse();
        System.out.println();
        node1.inOrderTraverse();
        System.out.println();
        List<Integer> list = node1.postTraverse();
        System.out.println(list);
    }
}

@Getter
@Setter
@NoArgsConstructor
class Node {
    // 名字
    private Integer name;
    // 左节点
    private Node left;
    // 右节点
    private Node right;

    public Node(Integer name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    public Node(Integer name) {
        this.name = name;
    }

    /**
     * 迭代法的前序遍历
     */
    public void preTraverse() {
        Deque<Node> stack = new LinkedList<>();
        // 加入队列
        stack.push(this);
        while (!stack.isEmpty()) {
            // 弹出
            Node node = stack.pop();
            System.out.print(node.name + "\t");
            if (node.right != null) {
                stack.push(node.right);
            }
            // 先取出左边
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 迭代的中序遍历
     */
    public void inOrderTraverse() {
        Deque<Node> stack = new LinkedList<>();
        Node cur = this;
        while (!stack.isEmpty() || cur != null) {
            // 将左子树一直往stack里面push
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node node = stack.pop();
            System.out.print(node.name + "\t");
            if (node.right != null) {
                // 将右边往里面push
                cur = node.right;
            }
        }
    }

    /**
     * 后序遍历
     *
     * @return
     */
    public List<Integer> postTraverse() {
        Deque<Node> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        stack.push(this);
        while (!stack.isEmpty()) {
            // 弹栈
            Node node = stack.pop();
            // 压左边
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            list.add(0, node.name);

        }
        return list;
    }
}
